package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.BitProblem;

/**
 * https://leetcode.com/problems/single-number-ii/
 * every element appears three times except for one,
 * 136 137 260
 * Your algorithm should have a linear runtime complexity.
 * Could you implement it without using extra memory? 不等于O1空间啊!!!
 * <p>
 * a ^ 0 = 本身
 * a ^ a = 0
 * <p> 数电思路最合理
 * https://blog.csdn.net/orangehdc/article/details/45391245 太秀了
 * https://blog.csdn.net/jocyln9026/article/details/19397477 太秀了
 * https://blog.csdn.net/yutianzuijin/article/details/50597413 太秀了
 *
 * @author tzp
 * @since 2020/11/13
 */
public class LC137 implements BitProblem {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for (int n : nums) {
            int newOnes = (~n & ones & ~twos) | (n & ~ones & ~twos);
            twos = (~n & ~ones & twos) | n & ones & (~twos);
            ones = newOnes;
        }
        System.out.println(twos);
        return ones;
    }

    public static void main(String[] args) {
        System.out.println(new LC137().singleNumber(new int[]{2, 2, 3, 2}));
    }
}
